A <#211#>pair<#211#> (sometimes called a <#212#>dotted pair<#212#>) is a record structure with two fields called the car and cdr fields (for historical reasons). Pairs are created by the procedure <#213#>cons<#213#>. The car and cdr fields are accessed by the procedures <#214#>car<#214#> and <#215#>cdr<#215#>. The car and cdr fields are assigned by the procedures <#216#>set-car!<#216#> and <#217#>set-cdr!<#217#>.
Pairs are used primarily to represent lists. A list can
be defined recursively as either the empty list
The objects in the car fields of successive pairs of a list are the elements of the list. For example, a two-element list is a pair whose car is the first element and whose cdr is a pair whose car is the second element and whose cdr is the empty list. The length of a list is the number of elements, which is the same as the number of pairs.
The empty list<#227#>empty list<#227#> is a special object of its own type (it is not a pair); it has no elements and its length is zero.
The most general notation (external representation) for Scheme pairs is the ``dotted'' notation <#2032#>(<#230#>c<#230#> . <#231#>c<#231#>)<#2032#> where <#232#>c<#232#> is the value of the car field and <#233#>c<#233#> is the value of the cdr field. For example <#234#>(4 . 5)<#234#> is a pair whose car is 4 and whose cdr is 5. Note that <#235#>(4 . 5)<#235#> is the external representation of a pair, not an expression that evaluates to a pair.
A more streamlined notation can be used for lists: the elements of the
list are simply enclosed in parentheses and separated by spaces. The
empty list
and
are equivalent notations for a list of symbols.
A chain of pairs not ending in the empty list is called an <#242#>improper list<#242#>. Note that an improper list is not a list. The list and dotted notations can be combined to represent improper lists:
is equivalent to
Whether a given pair is a list depends upon what is stored in the cdr field. When the <#247#>set-cdr!<#247#> procedure is used, an object can be a list one moment and not the next:
Within literal expressions and representations of objects read by the
<#250#>read<#250#> procedure, the forms <#251#>datum<#251#><#252#>'<#252#>,
<#253#>datum<#253#>, <#254#>,<#254#><#255#>datum<#255#><#256#>,<#256#>, and
<#257#>,@<#257#><#258#>datum<#258#> denote two-element lists whose first elements are
the symbols <#259#>quote<#259#>, <#260#>quasiquote<#260#>, <#2033#><#261#>unquote<#261#><#2033#>, and
<#262#>unquote-splicing<#262#>, respectively. The second element in each case
is <#263#>datum<#263#>. This convention is supported so that arbitrary Scheme
programs may be represented as lists. <#264#>Can or need this be stated
more carefully?<#264#> That is, according to Scheme's grammar, every
<#265#>expression<#265#> is also a <#266#>datum<#266#> (see section~#datum#267>
0<#2044#>(cadr <#330#>pair<#330#>)<#2044#> 1<#331#>essential procedure<#331#>